package 分治;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-13
 */
public class 传送带 {
    public static int getMaxWeight(int[] weights) {
        int max = 0;
        for (int weight : weights) {
            max = Math.max(max, weight);
        }
        return max;
    }

    public static int getSumWeight(int[] weights) {
        int sum = 0;
        for (int weight : weights) {
            sum += weight;
        }
        return sum;
    }

    public static int shipWithInDays(int[] weights, int Day) {
        int min = getMaxWeight(weights);
        int max = getSumWeight(weights);
        while (min <= max) {
            int mid = min + (max - min) / 2;
            if (canShip(weights, mid, Day)) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }

    private static boolean canShip(int[] weights, int speed, int day) {
        int sum = 1;
        int temp = speed;
        for (int i = 0; i < weights.length; ) {
            if (speed - weights[i] >= 0) {
                speed -= weights[i];
                i++;
            } else {
                speed = temp;
                sum++;
            }
        }
        return sum <= day ? true : false;
    }

    public static void main(String[] args) {
        System.out.println(shipWithInDays(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5));
    }
}
